class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new int[0];
        }
        int rows = matrix.length;
        int columns = matrix[0].length;
        int[] ans = new int[rows * columns];
        int index = 0;//记录下标

        int left = 0;
        int right = columns - 1;
        int top = 0;
        int bottom = rows - 1;

        /**
        从左到右遍历上侧元素，依次为 (top,left)(top,right)。
        从上到下遍历右侧元素，依次为 (top+1,right)(bottom,right)。
        如果 left<right 且 top<bottom，则从右到左遍历下侧元素，依次为 (bottom,right−1)到 (bottom,left+1)，以及从下到上遍历左侧元素，依次为 (bottom,left) 到 (top+1,left)。

         */
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++) {
                ans[index++] = matrix[top][column];
            }
            for (int row = top + 1; row <= bottom; row++) {
                ans[index++] = matrix[row][right];
            }
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--) {
                    ans[index++] = matrix[bottom][column];
                }
                for (int row = bottom; row > top; row--) {
                    ans[index++] = matrix[row][left];
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return ans;
    }
}